The present invention relates to a method of generating test patterns for logic network devices which are used in computers, communication systems and other electrical equipment.
There are three conventional methods of generating test patterns for logic circuits. In the first method, a logic circuit is described as a pattern of gates, and an algorithm such as the D algorithm, PODEM or FAN, etc., can be applied to the pattern of gates. For details of the D algorithm, reference may be made to an article by J. Paul Roth, entitled "Diagnosis of Automata Failures: A Calculus and a Method", IBM Journal of Research and Development, Vol. 10, pp. 278-291, July 1966. For details of the PODEM algorithm, reference may be made to an article by Prabhakar Goel, entitled "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE TRANSACTIONS ON COMPUTERS, Vol. C-30, No. 3, pp. 215-222, March 1981. For details of the FAN algorithm, reference may be made to an article by Hideo Fujiwara et al, entitled "On the Acceleration of Test Generation Algorithms", IEEE TRANSACTIONS ON COMPUTERS, Vol. C-32, No. 12, pp. 1137-1144 December 1983.
The first method is essentially suitable for combinational networks, but is inefficient for use with sequential circuits. The use of the D-algorithm in testing sequential circuits has been discussed, e.g., by M. Breuer and A. Friedman in Diagnosis & Reliable Design of Digital Systems, published by Computer Science Press, Inc., 1976, pp. 90-100, but this has not proven entirely satisfactory. Furthermore, it is difficult to apply the method to large scale circuits because the method is based on a gate model.
In the second method, the subject circuits are functionally described, and the test patterns that show how to change each function in response to the failure are generated. For details of the second method, reference may be made to an article by Satish M. Thatte et al, entitled "User Testing Of Microprocessors", IEEE PROC. COMPCON Spring pp. 108-114, 1979.
It is difficult for the second method to reflect differences in circuit structure in the fault model, because there is no information about the structure of the circuit. Furthermore, it is difficult to apply the second method to a random logic circuit which is not functionally closed.
To solve these problems of the second method, the third method incorporates circuit structure information into the functional circuit model, and the test patterns are generated to activate each signal line in the circuit. For details of the third method, reference may be made to an article by M. Kawai et al, entitled "A High Level Test Pattern Generation Algorithm", IEEE Proc. Test Conf. pp. 346-352, 1983. This method is essentially intended for combinational networks and it cannot be used effectively for sequential circuits. More particularly, in a true combinational network the output at an observable node will immediately reflect the input at a controllable node, and testing can be accomplished by applying an input and immediately examining the output. In a sequential network, however, the signals are propagated through the network over a plurality of clock cycles before being reflected at the observable node. It is therefore not possible to merely provide an input signal or signals and examine the output at that time.